Determining proximity information and computing spatial relationships between virtual objects is a fundamental consideration in many areas of robotics, computer-aided design, computer graphics and virtual reality applications. As virtual objects have no real or physical existence, a virtual object is often characterized by a mathematical and/or geometric representation. As such, simulation of the interactions between virtual objects in a virtual environment is computational in nature.
Although a virtual object is not real, it may have a real counterpart, that is, the representation of the virtual object may describe or model a real object. For example, a robot navigating through a real environment may have an internal representation of that environment such as a mathematical description of itself, where each object is located and what space each object occupies in the environment. These mathematical descriptions of the objects in the internal representation of the environment, also referred to as models, must explain the physical environment with sufficient accuracy and detail and be responsive to changes in the real environment, such that the robot can navigate and perform the various tasks required of it in the physical environment. When a virtual object has an immediate real counterpart, the virtual object is sometimes referred to as an avatar.
In other examples, the virtual environment may not have a real or physical counterpart. In many video games, for example a flight simulator, the objects and environment in the simulation, though perhaps modeled to imitate real or physical objects and environments, have no immediate real counterpart.
The term “virtual object” or simply “object” refers to the representation of the object and not the real object itself. The terms “real” or “physical” will be used herein when describing objects having a physical existence. The acts involved in mathematically describing, or otherwise modeling virtual objects and environments is referred to generally as “representation.”
Since virtual objects exist as mathematical concepts, the spatial relationships between the objects and forces arising from such relationships are computational constructs. Such computations may include updating the representation of each virtual object according to motion or movement (e.g., translation, rotation, and/or deformation of the object), detecting collisions and/or at-a-distance forces between virtual objects, determining a response to collision forces, etc. The acts involved in computing relationships and/or interactions between virtual objects in a virtual environment is referred to generally as “simulation.” A simulation is often implemented as a computer program that is executed on one or more processors of a computer and/or computer system.
A simulation may be partially guided by input from a user, or otherwise externally instructed. For example, an interface device, such as a joystick, mouse, track ball, gimbal, etc., may be manipulated by a user to apply control signals to the simulation. For example, a user may manipulate a joystick to control the movement of a virtual object.
Typically, the effect of the user input or change enacted on a virtual object through the interface device is computed and rendered as feedback to the user. That is, a user may effect a change in one or more objects in a virtual environment, the representation of the environment may then be updated to reflect the change, interaction between objects caused by the user input detected and simulated, and the results reported back to the user. This type of feedback control loop is commonly used in virtual environments.
In some instances, a simulation is visually rendered to the user. That is, the virtual objects in an environment may be rendered to a display such that a user may observe the effects of his actions through the interface device. A simulation or portions of a simulation may also be haptically rendered. The term “haptic” refers to the sense of touch. As such, a haptic rendering refers to stimuli that is communicated through feel or touch sensations rather than through the more common use of visual stimuli. A virtual environment may employ both haptic and visual renderings of the events in a simulation.
Haptic sensations may be communicated, for example, as a force-feedback applied to the interface device manipulated by the user. In a haptic rendering, it may be important to communicate the sensation, for instance, of two virtual objects colliding, or the sensation of two objects that are in tactile contact with one another. As such, collision detection is often part of the computations involved in modifying a virtual environment in response to, for example, a user enacted movement, or in updating an environment to ensure that the proper state of the environment is being reported (i.e., updating an environment to ensure that feedback renderings accurately reflect the environment and the objects within the environment) to the user.